class Solution:
    def minInsertions(self, s: str) -> int:
        left, right = 0, len(s) - 1
        DP = [[-1 for __ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            DP[i][i] = 0

        def dp(left: int, right: int) -> int:
            if left > right:
                return 0

            if DP[left][right] != -1:
                return DP[left][right]

            if s[left] == s[right]:
                DP[left][right] = dp(left + 1, right - 1)
            else:
                DP[left][right] = min(dp(left + 1, right), dp(left, right - 1)) + 1

            return DP[left][right]

        return dp(left, right)
